package org.hot100.h023;

/**
 * @Author: wjy
 * @Date: 2021/12/10 10:45
 */
public class Solution {

    public static void main(String[] args) {

        ListNode listNode3 = new ListNode(5);
        ListNode listNode2 = new ListNode(4, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        ListNode listNode6 = new ListNode(4);
        ListNode listNode5 = new ListNode(3, listNode6);
        ListNode listNode4 = new ListNode(1, listNode5);

        ListNode listNode8 = new ListNode(6);
        ListNode listNode7 = new ListNode(2, listNode8);

        ListNode[] listNodes = {listNode1, listNode4, listNode7};

        Solution solution = new Solution();
        ListNode listNode = solution.mergeKLists(listNodes);

        while (true) {
            if (listNode == null) {
                break;
            }
            System.out.println(listNode.val);
            listNode = listNode.next;

        }

    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

/*    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }*/

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = (left + right) / 2;
        ListNode l1 = this.merge(lists, left, mid);
        ListNode l2 = this.merge(lists, mid + 1, right);
        return this.mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = this.mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = this.mergeTwoLists(l1, l2.next);
            return l2;
        }

    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}